using System;
using System.Collections.Generic;
using System.Text;

namespace MyCollections
{
    public class SortedDictionary<TKey, TValue> where TKey:IComparable<TKey>
    { // add, count ,indexer, print, enumerator (KeyValuePair<TKey, TValue>)

        internal Node<TKey, TValue> Root;

        public SortedDictionary()
        {
            Root = null;
        }

        public TValue this[TKey index] 
        {
            get
            {  if (Root == null) throw new KeyNotFoundException(); 
               return Find(Root, index); }
        }

        private TValue Find(Node<TKey, TValue> current, TKey index)
        {
            
            var cmp = index.CompareTo(current.Key);
            
            if (cmp == 0) { return current.Value; }

            if (cmp < 0 && current.Left != null)
            { return Find(current.Left,index); }
            if (cmp > 0 && current.Right != null)
            { return Find(current.Right,index); }

            throw  new KeyNotFoundException();

        }

        public int Count()
        {
            if (Root == null) return 0;
            return CountR(Root);
        }

        private int CountR(Node<TKey, TValue> current)
        {
            int leftCount;
            int rightCount;

            if (current.Left != null)
            {
                leftCount = CountR(current.Left);
            }
            else
            {
                leftCount = 0;
            }

            if (current.Right != null)
            {
                rightCount = CountR(current.Right);
            }
            else
            {
                rightCount = 0;
            }

            return 1 + leftCount + rightCount;
        }

        public string Print()
        {
            var sb = new StringBuilder();
            if (Root == null) return "Sorted Dictionary is Empty";
            PrintR(Root, sb);
            return sb.ToString();
        }

        private void PrintR(Node<TKey, TValue> current, StringBuilder sb)
        {
            if (current.Left != null)
            {
                PrintR(current.Left,sb);
            }

            sb=sb.Append(current.Value+"\n");

            if (current.Right != null)
            {
                PrintR(current.Right,sb);
            }

        }

        public void Add(TKey key, TValue value)
        {
            AddR(Root, key, value);
        }

        private void AddR(Node<TKey, TValue> current, TKey key, TValue value)
        {
            Node<TKey, TValue> temp;

            if (current == null)
            {
                current = new Node<TKey, TValue>();
                current.Key = key;
                current.Value = value;
                Root = current;
                return;
            }

            if (key.CompareTo(current.Key) == 0)
            {
                return;
            }

            if (key.CompareTo(current.Key) < 0)
            {
                if (current.Left != null)
                {
                    AddR(current.Left, key, value);
                }
                else
                {
                    temp = new Node<TKey, TValue>();
                    temp.Key = key;
                    temp.Value = value;
                    current.Left = temp;
                }
            }
            else if (key.CompareTo(current.Key) > 0) 
            {
                if (current.Right != null)
                {
                    AddR(current.Right, key, value);
                }
                else
                {
                    temp = new Node<TKey, TValue>();
                    temp.Key = key;
                    temp.Value = value;
                    current.Right = temp;
                }
            }
        }

        public SortedDictionaryEnumerator<TKey, TValue> GetEnumerator()
        {
            return new SortedDictionaryEnumerator<TKey,TValue>(this);
        }

    }
}